package com.fengye.algorithms.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/28 10:26
 **/
public class SubsetsII90 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subs = new ArrayList<>();
        Arrays.sort(nums);
        dfs(false,0, nums, res, subs);
        return res;
    }

    public void dfs(boolean choosePre, int cur, int[] nums, List<List<Integer>> res, List<Integer> subs) {
        if(cur == nums.length) {
            res.add(new ArrayList<>(subs));
            return;
        }

        dfs(false,cur+1, nums, res, subs);
        // 没有选择前一个数，并且当前数和前一个数相等，就不选了
        if(!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        // 考虑当前位置
        subs.add(nums[cur]);

        // 选择了前一个数
        dfs(true, cur+1, nums, res, subs);
        // 不考虑当前位置
        subs.remove(subs.size() - 1);
    }

    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subs = new ArrayList<>();
        dfs2(0, nums, res, subs);
        return res;
    }

    public void dfs2(int cur, int[] nums, List<List<Integer>> res, List<Integer> subs) {
        if(cur == nums.length) {
            List<Integer> t = new ArrayList<>(subs);
            Collections.sort(t);
            if(!res.contains(t)) {
                res.add(t);
            }
            return;
        }

        // 考虑当前位置
        subs.add(nums[cur]);
        dfs2(cur+1, nums, res, subs);
        // 不考虑当前位置
        subs.remove(subs.size() - 1);
        dfs2(cur+1, nums, res, subs);
    }
}
